#include "cfg.h"

extern simple_instr ** headofinstr;

/** print the list of copy expressions **/
// remove a simple instr from the instr list and free it.
void remove_simple_instr(simple_instr * target) {
    simple_instr * prev = target->prev;
    simple_instr * next = target->next;

    if(target == *headofinstr) {
        *headofinstr = next;
        if(next)
            next->prev = NULL;
    } 
    else if(prev) {
        prev->next = next;
        if(next)
            next->prev = prev;
    }

    target->next = NULL;
    target->prev = NULL;
    free_instr(target);
}

// remove a instr node from the numbered instr list and free it.
void remove_instr_node(instr_node * instr) {
    instr_node * prev = instr->previous;
    instr_node * next = instr->next;

    if(prev) {
        prev->next = next;
        if(next)
            next->previous = prev;
    }

    free(instr);
}

void switch_instr_node_to_nop(instr_node * target) {
    target->instr = new_instr(NOP_OP, simple_type_void);
    target->instr->u.base.dst = NO_REGISTER;
    target->instr->u.base.src1 = NO_REGISTER;
    target->instr->u.base.src2 = NO_REGISTER;
}


void print_copy_expressions(instr_ptr * copy_instrs) {
    instr_ptr * current_copy_instr = copy_instrs;

    while(current_copy_instr) {
        fprintf(stdout, "%d\t%d ", current_copy_instr->number, current_copy_instr->instr->number);
        fprint_instr(stdout, current_copy_instr->instr->instr);
        //fprintf(stdout, "\n");
        current_copy_instr = current_copy_instr->next;
    }
}

int find_copy_expressions(instr_ptr ** copy_instrs, instr_node * instrs) {
    instr_node * current_instr = instrs;
    instr_ptr * last_instr_ptr =  NULL;
    int totalcopyexpressions = 0;

    while(current_instr) { // traverse through the instructions
        simple_instr * instr = current_instr->instr;
        if(instr->opcode == CPY_OP 
            //&& instr->u.base.src1->kind == PSEUDO_REG
            && instr->u.base.dst->kind == PSEUDO_REG 
            && instr->u.base.src2 == NULL) {
                instr_ptr * copyinstr = (instr_ptr *) malloc(sizeof(instr_ptr));
                copyinstr->number = totalcopyexpressions++;
                copyinstr->instr = current_instr;
                copyinstr->next = NULL;
                if(*copy_instrs == NULL) {
                    *copy_instrs = copyinstr;
                    last_instr_ptr = copyinstr;
                } else {
                    last_instr_ptr->next = copyinstr;
                    last_instr_ptr = last_instr_ptr->next;
                }
        }
        current_instr = current_instr->next;
    }    

    return totalcopyexpressions;
}

void free_instr_ptr(instr_ptr * copy_instrs) {
    instr_ptr * current_instr = copy_instrs;
    instr_ptr * next_instr = NULL;

    while(current_instr) {
        next_instr = current_instr->next;
        free(current_instr);
        current_instr = next_instr;
    }
}


instr_ptr * find_copy_instr(instr_ptr * copy_instrs, simple_instr * instr) {
    instr_ptr * current_copy_instr = copy_instrs;

    while(current_copy_instr) {
        simple_instr * copy_instr = current_copy_instr->instr->instr;
        if(copy_instr == instr)
        //if(copy_instr->u.base.src1 == instr->u.base.src1 && copy_instr->u.base.dst == instr->u.base.dst)
            return current_copy_instr;
        current_copy_instr = current_copy_instr->next;
    }

    return NULL;
}

void print_copy_expr(basic_block_node * block_head) {
	basic_block_node * current_block;
	int i =0;	

	for(current_block = block_head; current_block; current_block = current_block->next) {
		printf("copy %d ", current_block->number);
		for(i = 0; i < current_block->ac_copy->num_bits; i++)
			printf("%d", get_bit(current_block->ac_copy, i));
		printf("\n");
       
        printf("kill %d ", current_block->number);
		for(i = 0; i < current_block->ac_kill->num_bits; i++)
			printf("%d", get_bit(current_block->ac_kill, i));
		printf("\n");

        printf("acin %d ", current_block->number);
		for(i = 0; i < current_block->acin->num_bits; i++)
			printf("%d", get_bit(current_block->acin, i));
		printf("\n");

        printf("acout %d ", current_block->number);
		for(i = 0; i < current_block->acout->num_bits; i++)
			printf("%d", get_bit(current_block->acout, i));
		printf("\n\n");
	}
	printf("\n");
}


void eval_copy_and_kill_sets(basic_block_node * block_head, instr_ptr * copy_instrs, int totalcopyinstrs) {
    basic_block_node * current_block = block_head;
    instr_node * current_instr;
    instr_ptr * copyinstr;
    instr_ptr * find_result;

    while(current_block) {
        current_block->ac_copy = new_bit_vector(totalcopyinstrs);   // intialize the bit vectors
        current_block->ac_kill = new_bit_vector(totalcopyinstrs);
        current_block->acin = new_bit_vector(totalcopyinstrs);
        current_block->acout = new_bit_vector(totalcopyinstrs);

        for(current_instr = current_block->start; current_instr && current_instr != current_block->end->next; current_instr = current_instr->next) {
            simple_instr * instr = current_instr->instr;           
            
            for(copyinstr = copy_instrs; copyinstr; copyinstr = copyinstr->next) {
                simple_instr * cinstr = copyinstr->instr->instr;
                switch(simple_op_format(instr->opcode)) {
                    case BASE_FORM: {
			            find_result = NULL;	    
			            if(instr->opcode == CPY_OP) {
				            find_result = find_copy_instr(copy_instrs, instr);

	            			if(find_result) {                            
    			        		set_bit(current_block->ac_copy, find_result->number, TRUE);									        
                                set_bit(current_block->ac_kill, find_result->number, FALSE);
				            }
			            }
                        
                        if(!find_result && instr->u.base.dst && (instr->u.base.dst == cinstr->u.base.dst || instr->u.base.dst == cinstr->u.base.src1)) {                            
                            set_bit(current_block->ac_copy, copyinstr->number, FALSE);
                            set_bit(current_block->ac_kill, copyinstr->number, TRUE);			    
                        }
                        break;
                    }                        
		            case LDC_FORM: {
			            if(instr->u.ldc.dst && (instr->u.ldc.dst == cinstr->u.base.dst || instr->u.ldc.dst == cinstr->u.base.src1)) {
				            set_bit(current_block->ac_copy, copyinstr->number, FALSE);
				            set_bit(current_block->ac_kill, copyinstr->number, TRUE);
			            }
			            break;
		            }
		            case CALL_FORM: {
			            if(instr->u.call.dst && (instr->u.call.dst == cinstr->u.base.dst || instr->u.call.dst == cinstr->u.base.src1)) {
				            set_bit(current_block->ac_copy, copyinstr->number, FALSE);
				            set_bit(current_block->ac_kill, copyinstr->number, TRUE);
			            }
			            break;
		            }
                }
            }
        }

        current_block = current_block->next;
    }
}




int ac_meetop(basic_block_node * block) {
    block_ptr * predecessor = block->predecessor;

    if(predecessor)
        set_all_bits(block->acin, TRUE);
    else set_all_bits(block->acin, FALSE);

    while(predecessor) {
        and_bits(block->acin, predecessor->block->acout);
        predecessor = predecessor->next;
    }

    return FALSE;
}

int ac_transferfunc(basic_block_node * block) {
    bit_vector * oldout = new_bit_vector(block->acout->num_bits);

	copy_bits(oldout, block->acout);

	copy_bits(block->acout, block->acin);
	subtract_bits(block->acout, block->ac_kill);
	or_bits(block->acout, block->ac_copy);

	return !bits_are_equal(oldout, block->acout);
}


void free_block_ptr(block_ptr * head) {
    block_ptr * current = head;
    block_ptr * next = NULL;

    while(current) {
        next = current->next;
        free(current);
        current = next;
    }
}

// creates a list of definitions ( Reaching Definitions )
int find_definitions(instr_node * instr_head, instr_ptr ** def_instrs) {
    instr_node * current_instr = NULL;
    instr_ptr * last_def = NULL;
    int number = 0;
    // go thru list of instructions
    for(current_instr = instr_head; current_instr; current_instr = current_instr->next) {
        if(current_instr->instr->opcode == CPY_OP) { // copy instructions are new definitions
            instr_ptr * tmp = (instr_ptr *) malloc(sizeof(instr_ptr));
            tmp->instr = current_instr;
            tmp->number = number++;
            tmp->next = NULL;
            if(*def_instrs) {
                last_def->next = tmp;                
            }
            else {
                *def_instrs = tmp;
            }
            last_def = tmp;
        }
    }

	return number;
}


void add_rd_node(rdef_node ** rdhead, simple_reg * r, instr_ptr * instr) {
    rdef_node * newrd = (rdef_node *) malloc(sizeof(rdef_node));
    newrd->instr = instr;
    newrd->r = r;
    
    newrd->next = *rdhead;
    *rdhead = newrd;    
}

rdef_node * find_by_dst_reg(rdef_node * rdhead, simple_reg * r, instr_ptr * upto) {
    rdef_node * current = rdhead;
    rdef_node * result = NULL;
    while(current && current->instr != upto)
    {
        if(current->r == r)
            result = current;

        current = current->next;
    }

    return NULL;
}

rdef_node * find_rdef(rdef_node * rdhead, simple_reg * r) {
    rdef_node * current = rdhead;
    
    while(current)
    {
        if(current->r == r)
            return current;

        current = current->next;
    }

    return NULL;
}

void free_rd_node(rdef_node * rdhead) {
    rdef_node * current = rdhead, * next;

    while(current) {
        next = current->next;
        free(current);
        current = next;
    }
}

void init_rd_gen_and_kill_sets(basic_block_node * block_head, instr_ptr * def_instrs, int totaldefs) {
    basic_block_node * current_block;
    instr_ptr * current_def = def_instrs;

	//printf("total defs = %d\n", totaldefs);

    for(current_block = block_head; current_block; current_block = current_block->next) {
        instr_node * current_instr = current_block->start;
        rdef_node * rdhead = NULL;
        instr_ptr * kill_def = def_instrs;
        current_block->rdgen = new_bit_vector(totaldefs);
        current_block->rdin = new_bit_vector(totaldefs);
        current_block->rdkill = new_bit_vector(totaldefs);
        current_block->rdout = new_bit_vector(totaldefs);
        
        if(current_instr) {            
            for(; current_def && current_instr != current_block->end->next; current_instr = current_instr->next) {
                if(current_instr == current_def->instr) {
                    rdef_node * find_def = find_by_dst_reg(rdhead, current_instr->instr->u.base.dst, current_def);
                    set_bit(current_block->rdgen, current_def->number, TRUE);
                    add_rd_node(&rdhead, current_instr->instr->u.base.dst, current_def);
                    if(find_def) {
                        set_bit(current_block->rdgen, find_def->instr->number, FALSE);
                    }
                    current_def = current_def->next;
                }
            }            
            for(; kill_def ; kill_def = kill_def->next) {
		//printf("current_block = %p\n", kill_def->instr->block);
                if(kill_def->instr->block != current_block && find_rdef(rdhead, kill_def->instr->instr->u.base.dst)) {
			//printf("currt_block = %p %p kb=%d cb=%d rdkill=%d\n", kill_def->instr->block, current_block, kill_def->instr->block->number, current_block->number, kill_def->number);
                    set_bit(current_block->rdkill, kill_def->number, TRUE);
		}
            }
	    copy_bits(current_block->rdout, current_block->rdgen);
        }
	        
        free_rd_node(rdhead);
    }
}


void print_rdef(basic_block_node * block_head) {
    basic_block_node * current_block = block_head->next;
    for(; current_block; current_block = current_block->next) {
        int i;
        printf("block # %d\nrdgen: ", current_block->number);
        for(i = 0; i < current_block->rdgen->num_bits; i++)
            if(get_bit(current_block->rdgen, i))
                printf("%d ", i);

        printf("\nrdkill: ");
        for(i = 0; i < current_block->rdgen->num_bits; i++)
            if(get_bit(current_block->rdkill, i))
                printf("%d ", i);
	
	
		printf("\nrdin: [%d] ", current_block->rdin->num_bits);		
        for(i = 0; i < current_block->rdin->num_bits; i++)
            if(get_bit(current_block->rdin, i))
                printf("%d ", i);
	
		printf("\nrdout: ");
        for(i = 0; i < current_block->rdout->num_bits; i++)
            if(get_bit(current_block->rdout, i))
                printf("%d ", i);
        printf("\n\n");
	
    }
}

int rd_meetop(basic_block_node * block) {
    block_ptr * predecessor = block->predecessor;

    //printf("rd_meetop b # %d\n", block->number);
//    if(predecessor)
  //      set_all_bits(block->rdin, TRUE);
    //else
		set_all_bits(block->rdin, FALSE);

    while(predecessor) {
        or_bits(block->rdin, predecessor->block->rdout);
        predecessor = predecessor->next;
    }

    return FALSE;
}

int rd_transferfunc(basic_block_node * block) {
	bit_vector * oldout = new_bit_vector(block->rdout->num_bits);

	copy_bits(oldout, block->rdout);

	copy_bits(block->rdout, block->rdin);
	subtract_bits(block->rdout, block->rdkill);
	or_bits(block->rdout, block->rdgen);

	return !bits_are_equal(oldout, block->rdout);
}

instr_ptr * get_def_instr_by_num(instr_ptr * def_instrs, int num) {
	instr_ptr * current_def = def_instrs;

	while(current_def) {
		if(current_def->number == num)
			return current_def;
		current_def = current_def->next;
	}
}


void update_use_def(rdef_node * rdef_head, instr_node * instr, simple_reg * r) {
	rdef_node * current_def = rdef_head;

	while(current_def) {
		if(current_def->r == r)
			set_bit(instr->defs, current_def->instr->instr->number, TRUE);
		//printf("here 2\n");
		current_def = current_def->next;
	}
}

void update_use_def_for_label(instr_ptr * lbl_head, instr_node * instr, simple_sym * lab) {
	instr_ptr * current_label = lbl_head;

	while(current_label) {
		if(current_label->instr->instr->u.label.lab == lab) {
			set_bit(instr->defs, current_label->instr->number, TRUE);
			break;
		}
		current_label = current_label->next;
	}
}

void remove_def_for_reg(rdef_node ** rdef_head, simple_reg * r) {
	rdef_node * current_def;
	rdef_node * prev_def;

	//printf("entered: remove_def_for_reg\n");
	// remove definition of r from the head
	while(*rdef_head && (*rdef_head)->r == r) {
		prev_def = *rdef_head;
		*rdef_head = (*rdef_head)->next;
		free(prev_def);
	}
	
	for(current_def = *rdef_head, prev_def = NULL; current_def;) {
		if(current_def->r == r) {
			prev_def->next = current_def->next;
			free(current_def);
			current_def = prev_def->next;
			continue;
		}
		prev_def = current_def;
		current_def = current_def->next;
	}
	//printf("exited: remove_def_for_reg\n");
}

void calculate_use_def_chain(basic_block_node * block_head, int totalinstrs, instr_ptr * def_instrs, instr_node * instr_head) {
	basic_block_node * current_block = block_head;
	instr_ptr * label_head =  NULL;
	instr_node * current_instr = instr_head;

	while(current_instr) {
		if(current_instr->instr->opcode == LABEL_OP) {
			instr_ptr * tmp = (instr_ptr *) malloc(sizeof(instr_ptr));
			tmp->instr = current_instr;
			tmp->next = label_head;
			label_head = tmp;
		}
		current_instr = current_instr->next;
	}

	while(current_block) {
		rdef_node * block_defs = NULL;
		instr_ptr * block_labels = NULL;				
		int i = 0;
		current_instr = current_block->start;
		for(i = 0; i < current_block->rdin->num_bits; i++)
		{
			if(get_bit(current_block->rdin, i)) {
				instr_ptr * def_instr = get_def_instr_by_num(def_instrs, i);
				add_rd_node(&block_defs, def_instr->instr->instr->u.base.dst, def_instr);
			}
		}

		while(current_instr && current_instr != current_block->end->next) {
			simple_instr * instr = current_instr->instr;
			current_instr->defs = new_bit_vector(totalinstrs);
			
			switch(simple_op_format(instr->opcode)) {
				case BASE_FORM: {
					if(instr->u.base.src1) {
						update_use_def(block_defs, current_instr, instr->u.base.src1);
					}
					if(instr->u.base.src2) {
						update_use_def(block_defs, current_instr, instr->u.base.src2);
					}
					if(instr->u.base.dst) {
						instr_ptr * cinstr_ptr = (instr_ptr *) malloc(sizeof(instr_ptr));
						cinstr_ptr->instr = current_instr;

						remove_def_for_reg(&block_defs, instr->u.base.dst);
						add_rd_node(&block_defs, instr->u.base.dst, cinstr_ptr);
					}
					break;
				}
				case BJ_FORM: {
					if(instr->u.bj.src) 
						update_use_def(block_defs, current_instr, instr->u.bj.src);
					if(instr->u.bj.target) 
						update_use_def_for_label(label_head, current_instr, instr->u.bj.target);
					break;
				}
				case LDC_FORM: {
					if(instr->u.ldc.dst) {
						instr_ptr * cinstr_ptr = (instr_ptr *) malloc(sizeof(instr_ptr));
						cinstr_ptr->instr = current_instr;

						remove_def_for_reg(&block_defs, instr->u.ldc.dst);
						add_rd_node(&block_defs, instr->u.ldc.dst, cinstr_ptr);
					}				
					break;
				}
				case CALL_FORM: {
					int i;
					if(instr->u.call.dst) {
						instr_ptr * cinstr_ptr = (instr_ptr *) malloc(sizeof(instr_ptr));
						cinstr_ptr->instr = current_instr;

						remove_def_for_reg(&block_defs, instr->u.ldc.dst);
						add_rd_node(&block_defs, instr->u.ldc.dst, cinstr_ptr);
					}
					if(instr->u.call.proc) {
						update_use_def(block_defs, current_instr, instr->u.call.proc);
					}
					for(i = 0; i < instr->u.call.nargs; i++)
					{
						update_use_def(block_defs, current_instr, instr->u.call.args[i]);
					}
					break;
				}
				case MBR_FORM: {
					int i;
					if(instr->u.mbr.src) {
						update_use_def(block_defs, current_instr, instr->u.mbr.src);
					}
					for(i = 0; i < instr->u.mbr.ntargets; i++)
						update_use_def_for_label(label_head, current_instr, instr->u.mbr.targets[i]);
					if(instr->u.mbr.deflab) {
						update_use_def_for_label(label_head, current_instr, instr->u.mbr.deflab);
					}
					break;
				}
			}
			//printf("here 1\n");
			current_instr = current_instr->next;
		}
		free_rd_node(block_defs);
		current_block = current_block->next;
	}

	//printf("exited: calculate_use_def_chain\n");
}


void print_use_def_chain(basic_block_node * block_head) {
	basic_block_node * current_block = block_head;

	while(current_block) {
		instr_node * current_instr = current_block->start;
		printf("block # %d\n", current_block->number);
		while(current_instr && current_instr != current_block->end->next) {
			int i;
			printf("%3d ", current_instr->number);
			fprint_instr(stdout, current_instr->instr);
			printf("\n\tDefined at: ");

			for(i=0; i<current_instr->defs->num_bits; i++)
				if(get_bit(current_instr->defs, i))
					printf("%d ", i);
			printf("\n");
			current_instr = current_instr->next;
		}
		current_block = current_block->next;
	}
}

void add_instr_ptr(instr_ptr ** head, instr_node * instr) {
	instr_ptr * tmp = (instr_ptr *) malloc(sizeof(instr_ptr));
	tmp->instr = instr;
	tmp->next = *head;

	*head = tmp;
}

/**
 * Mark
 *	CALL_OP
 *  RET_OP
 *  JMP_OP
 *		as essentials
 **/
void init_essential_instructions(instr_node * instr_head, instr_ptr ** worklist, bit_vector * essentialInstrs) {
	instr_node * current_instr = instr_head;

	while(current_instr) {
        switch(current_instr->instr->opcode) {
            case CALL_OP:
            case RET_OP:
            case JMP_OP:
            case STR_OP:
            case MCPY_OP:
                set_bit(essentialInstrs, current_instr->number, TRUE);
			    add_instr_ptr(worklist, current_instr);
                break;
        }
        /*
		if(current_instr->instr->opcode == CALL_OP) {
			set_bit(essentialInstrs, current_instr->number, TRUE);
			add_instr_ptr(worklist, current_instr);
		} else if(current_instr->instr->opcode == RET_OP) {
			set_bit(essentialInstrs, current_instr->number, TRUE);
			add_instr_ptr(worklist, current_instr);
		} else if(current_instr->instr->opcode == JMP_OP) {
			set_bit(essentialInstrs, current_instr->number, TRUE);
			add_instr_ptr(worklist, current_instr);
		}
        */
		current_instr = current_instr->next;
	}
}


instr_ptr * pop_instr_ptr(instr_ptr ** head) {
	instr_ptr * tmp = *head;
	if(*head)
		*head = (*head)->next;

	return tmp;
}

instr_node * get_ith_instr(instr_node * instr_head, int i) {
	instr_node * current_instr = instr_head;
	while(current_instr) {
		if(current_instr->number == i)
			return current_instr;
		current_instr = current_instr->next;
	}
}
void do_dead_code_elimination(basic_block_node * block_head, instr_node * instr_head, int totalinstrs, int blockCount) {
    instr_ptr * def_instrs = NULL;
    int totalrdefs = 0;
    block_ptr * stack = NULL;
	instr_ptr * worklist = NULL;
	bit_vector * essentialInstrs = new_bit_vector(totalinstrs);
	int isChangedEI = 1, j;
    
    totalrdefs = find_definitions(instr_head, &def_instrs);
    init_rd_gen_and_kill_sets(block_head, def_instrs, totalrdefs);
    find_predecessors(block_head);
    while(dfa_start(block_head, rd_meetop, rd_transferfunc, &stack, 0)) {
        free_block_ptr(stack);
		stack = NULL;
    }
	
	calculate_use_def_chain(block_head, totalinstrs, def_instrs, instr_head);
	
	init_essential_instructions(instr_head, &worklist, essentialInstrs);

	// compute essential instructions
	while(isChangedEI) {
		instr_node * current_instr = instr_head;
		isChangedEI = 0;		
		while(worklist) {
			instr_ptr * current_essential_instr = pop_instr_ptr(&worklist);
			int i;

			//printf("popping instr # %d\n", current_essential_instr->instr->number);
			for(i=0; i < current_essential_instr->instr->defs->num_bits; i++) {
				if(get_bit(current_essential_instr->instr->defs, i)) {
					if(!get_bit(essentialInstrs, i)) {
						set_bit(essentialInstrs, i, TRUE);
						add_instr_ptr(&worklist, get_ith_instr(instr_head, i) );						
						isChangedEI = 1;
					}
				}
			}
		}

		find_dominators(block_head, blockCount);

		for(j = 0; j < essentialInstrs->num_bits; j++) {
			if(!get_bit(essentialInstrs, j)) {
				instr_node * j_instr = get_ith_instr(instr_head, j);
				
				while(current_instr) {
					if(current_instr->instr->opcode == BFALSE_OP || current_instr->instr->opcode == BTRUE_OP) {
						if(get_bit(current_instr->block->dom, j_instr->block->number)) {
							set_bit(essentialInstrs, current_instr->number, TRUE);
							add_instr_ptr(&worklist, current_instr );
						}
					}
					current_instr = current_instr->next;
				}
			}
		}
	}
	
	
	//printf("essential instructions: ");
	for(j = 0; j < essentialInstrs->num_bits; j++)
		if(get_bit(essentialInstrs, j)) {
			//printf("%d ", j);
		} else {
			instr_node * j_instr = get_ith_instr(instr_head, j);
			remove_simple_instr(j_instr->instr);
			switch_instr_node_to_nop(j_instr);
		}
	//printf("\n");
	
	//print_use_def_chain(block_head);
//	print_blocks(block_head);
    free_instr_ptr(def_instrs);
	free_instr_ptr(worklist);
}

void do_copy_propagation(basic_block_node ** block_head, instr_node ** instr_head, simple_instr * inlist, int * blockCount, int * instrCount) {
    block_ptr * stack = NULL;
    basic_block_node * current_block = *block_head;
    int totalcopyexpressions = 0;
    instr_ptr * copy_instrs = NULL;

    totalcopyexpressions = find_copy_expressions(&copy_instrs, *instr_head);       
    eval_copy_and_kill_sets(*block_head, copy_instrs, totalcopyexpressions);
    
    while(dfa_start(*block_head, ac_meetop, ac_transferfunc, &stack, 0)) {
        free_block_ptr(stack);
		stack = NULL;
	}

    // printing
    //print_blocks(*block_head);
    //printf("found %d copy instructions.\n", totalcopyexpressions);
   // print_copy_expressions(copy_instrs);   
    //print_copy_expr(*block_head);
    
    while(current_block) {
        instr_ptr * current_cinstr;
        int i = 0;
        if(current_block->start) // skip entry & exit block
        for(current_cinstr = copy_instrs; current_cinstr; current_cinstr = current_cinstr->next, i++) {
            if(get_bit(current_block->acin, i) ) {
                // current_cinstr->dst is available at this block&& get_bit(current_block->acout, i)
                // if it is a constant, lets recreate the constant in this block
                // else replace the dst's reference with the source
                simple_instr * cinstr = current_cinstr->instr->instr;
                simple_instr * linstr = current_cinstr->instr->instr->prev;               
                
               // printf("here 1 b # %d (%d)\n", current_block->number, i);

                if(linstr && linstr->opcode == LDC_OP) {
                    simple_instr * new_ldc = new_instr(LDC_OP, cinstr->type); // create ldc
                    simple_instr * new_cpy = new_instr(CPY_OP, cinstr->type); // create cpy

                   // printf("here 2\n");
                    
                    
                    new_ldc->next = new_cpy;
                    new_ldc->u.ldc.dst = new_register(cinstr->type, TEMP_REG);
                    new_ldc->u.ldc.value.format = cinstr->prev->u.ldc.value.format;                    
                    if(new_ldc->u.ldc.value.format == IMMED_INT) {
                        new_ldc->u.ldc.value.u.ival = linstr->u.ldc.value.u.ival;
                    } else {
                        new_ldc->u.ldc.value.u.fval = linstr->u.ldc.value.u.fval;
                    }

                    new_cpy->prev = new_ldc;
                    
                    new_cpy->u.base.dst = cinstr->u.base.dst;
                    new_cpy->u.base.src1 = new_ldc->u.ldc.dst;

                    if(current_block->start->instr->opcode == LABEL_OP) {
                        new_ldc->prev = current_block->start->instr;   
                        new_cpy->next = current_block->start->instr->next;
                        if(current_block->start->instr->next)
                            current_block->start->instr->next->prev = new_cpy;
                        current_block->start->instr->next = new_ldc;
                    } else {
                        new_ldc->prev = current_block->start->instr->prev;   
                        new_cpy->next = current_block->start->instr;
                        if(current_block->start->instr->prev)
                            current_block->start->instr->prev->next = new_ldc;
                        current_block->start->instr->prev = new_cpy;
                        current_block->start->instr = new_ldc;
                    }
                }
            }
        }
        current_block = current_block->next;
    }

    *instr_head = NULL;
    *block_head = NULL;

    // re-number the instructions
    *instrCount = number_instrs(instr_head, inlist);

    // re-calculate the basic blocks
    *blockCount = find_basic_block (block_head, *instr_head);
   
    free_instr_ptr(copy_instrs);
}




// constant folding

void remove_constant_reg(constant_reg * constant) {
    constant_reg * prev = constant->prev;
    constant_reg * next = constant->next;

    if(prev) {
        prev->next = next;
        if(next)
            next->prev = prev;
    }
    constant->instr = NULL;
    constant->next = NULL;
    constant->prev = NULL;
    constant->r = NULL;    
    free(constant);
}

constant_reg * isConstant(simple_reg * r, constant_reg * constants) {
    constant_reg * constant = constants;

    while(constant) {
        if(constants->instr) {
            switch(constant->instr->instr->opcode) {
                case LDC_OP: {
                    if(constant->instr->instr->u.ldc.dst == r)
                        return constant;
                    break;
                }
                case CPY_OP: {
                    if(constant->instr->instr->u.base.dst == r) 
                        return constant;
                    break;
                }
            }
        } else {
            if(constant->r == r)
                return constant;
        }
        constant = constant->next;
    }

    return NULL;
}

void add_constant(constant_reg ** head, constant_reg * newconstant) {
    newconstant->next = *head;
    newconstant->prev = NULL;
    if(*head)
        (*head)->prev = newconstant;
    *head = newconstant;
}

void print_constants(constant_reg * head) {
    constant_reg * current_constant = head;
    while(current_constant) {
        printf("instr %d reg = \t", current_constant->instr->number);
        fprint_reg(stdout, current_constant->r);
        printf("\n");
        current_constant = current_constant->next;
    }
}

void add_label_node(label_node ** head, simple_sym * l) {
    label_node * temp = (label_node*)malloc(sizeof(label_node));
    temp->l = l;
    temp->next = *head;
    *head = temp;        
}

int do_constant_folding(basic_block_node * block_head) {    
    basic_block_node * current_block = block_head;    
    instr_node * current = NULL;
    label_node * cleanuplist = NULL;
    int rerun = 0;
    while(current_block) {
        constant_reg * constants = NULL;
    
        current = current_block->start;
        while(current && current != current_block->end->next) {
            simple_instr * instr = current->instr;
            switch(simple_op_format(instr->opcode)) {
                case BASE_FORM: {
                    constant_reg * r1 = NULL, * r2 = NULL;
                    r1 = isConstant(instr->u.base.src1, constants); // check if the src1 is constant
                    r2 = isConstant(instr->u.base.src2, constants); // check if src2 is constant
                    
                    if(r1 && r2) {                        
                        int isInt = r1->value.format == IMMED_INT && r2->value.format == IMMED_INT; // is final result int or float ?
                        int iresult, ir1, ir2;
                        float fresult, fr1, fr2;
                        int constantFolded = 0;

                        if(isInt) {
                            ir1 = r1->value.u.ival;
                            ir2 = r2->value.u.ival;
                        } else {
                            fr1 = r1->value.u.fval;
                            fr2 = r2->value.u.fval;
                        }

                        switch(instr->opcode) {
                            case ADD_OP: {                                
                                constantFolded = 1;
                                if(isInt) iresult = ir1 + ir2;
                                else fresult = fr1 + fr2;                                
                                break;
                            }
                            case MUL_OP: {
                                constantFolded = 1;
                                if(isInt)
                                    iresult = ir1 * ir2;
                                else fresult = fr1 * fr2;
                                //printf("can constant fold instr # %d\niresult = %d  fresult= %f\n", current->number, iresult, fresult);
                                break;
                            }                            
                            case SUB_OP: {
                                constantFolded = 1;
                                if(isInt)
                                    iresult = ir1 - ir2;
                                else fresult = fr1 - fr2;
                                break;
                            }
                            
                            case DIV_OP: {
                                constantFolded = 1;
                                if(isInt)
                                    if(ir2)
                                        iresult = ir1 / ir2;
                                    else constantFolded = 0;
                                else 
                                    if(fr2)
                                        fresult = fr1 / fr2;
                                    else constantFolded = 0;
                                //printf("div constant folded at # %d\niresult = %d  fresult= %f\n", current->number, iresult, fresult);
                                break;
                            }
                            case SL_OP: {
                                constantFolded = 1;
                                if(isInt)
                                    iresult = ir1 < ir2 ? 1 : 0;
                                else
                                    fresult = fr1 < fr2 ? 1 : 0;
                                break;
                            }
                            case SLE_OP: {
                                constantFolded = 1;
                                if(isInt)
                                    iresult = ir1 < ir2 ? 1 : 0;
                                else
                                    fresult = fr1 < fr2 ? 1 : 0;
                                break;
                            }
                            case SNE_OP: {
                                constantFolded = 1;
                                if(isInt)
                                    iresult = ir1 != ir2 ? 1 : 0;
                                else
                                    fresult = fr1 != fr2 ? 1 : 0;
                                break;
                            }
                            case SEQ_OP: {
                                constantFolded = 1;
                                if(isInt)
                                    iresult = ir1 == ir2 ? 1 : 0;
                                else
                                    fresult = fr1 == fr2 ? 1 : 0;
                                break;
                            }
                        }
                        
                        if(constantFolded) {
                            // add the ld instruction to the list of instruction, numbered instruction and constants
                            constant_reg * temp = (constant_reg *)malloc(sizeof(constant_reg));
                            instr_node * newinstr = (instr_node *)malloc(sizeof(instr_node));

                            // creating a simple instr
                            simple_instr * ldcinstr = new_instr(LDC_OP, simple_type_signed);
                            rerun = 1;

                            if(isInt) {                                
                                ldcinstr->u.ldc.dst = instr->u.base.dst;
                                ldcinstr->u.ldc.value.format = IMMED_INT;
                                ldcinstr->u.ldc.value.u.ival = iresult;
                            } else {                                
                                ldcinstr->u.ldc.dst = instr->u.base.dst;
                                ldcinstr->u.ldc.value.format = IMMED_FLOAT;
                                ldcinstr->u.ldc.value.u.fval = fresult;                        
                            }

                            // adding the instruction to 
                            if(instr->prev) {
                                instr->prev->next = ldcinstr;
                                ldcinstr->next = instr->next;
                                if(instr->next) {
                                    instr->next->prev = ldcinstr;
                                }
                                instr->next = NULL;
                                instr->prev = NULL;
                                current->instr = ldcinstr;
                            }

                            newinstr->block = current_block;
                            newinstr->instr = ldcinstr;
                            newinstr->next = current->next;
                            newinstr->previous = current->previous;
                            newinstr->number = current->number;

                            if(current->previous) {
                                current->previous->next = newinstr;
                                if(current->next) {
                                    current->next->previous = newinstr;
                                }
                            }
                            current->previous = NULL;
                            current->next = NULL;
                            free(current);
                            current = newinstr;

                            temp->instr = current;                            
                            temp->value.format = ldcinstr->u.ldc.value.format;
                            if(temp->value.format == IMMED_INT) {
                                temp->value.u.ival = ldcinstr->u.ldc.value.u.ival;
                            } 
                            else if(temp->value.format == IMMED_FLOAT)
                            {
                                temp->value.u.fval = ldcinstr->u.ldc.value.u.fval;
                            }
                            
                            temp->r = ldcinstr->u.ldc.dst; 
                            add_constant(&constants, temp);

                            // do i need to remove the old ldc instructions ?
                            if(r1->instr->instr->opcode == LDC_OP) {
                                printf("instruction removed at %d\n", r1->instr->number);
                                remove_simple_instr(r1->instr->instr);
                                switch_instr_node_to_nop(r1->instr);
                                //remove_constant_reg(r1);                                
                            }
                            if(r2->instr->instr->opcode == LDC_OP) {
                                printf("instruction removed at %d\n", r2->instr->number);
                                remove_simple_instr(r2->instr->instr);
                                switch_instr_node_to_nop(r2->instr);
                                //remove_constant_reg(r2);                                
                            }
                        }
                    }

                    if(instr->opcode == CPY_OP) {
                        constant_reg * r1 = isConstant(instr->u.base.src1, constants);
                        if(r1) {
                            constant_reg * temp = (constant_reg *) malloc(sizeof(constant_reg));
                            temp->next = NULL;
                            temp->instr =  current;
                            temp->r = instr->u.base.dst;                            
                            if(temp->value.format == IMMED_INT) {
                                temp->value.u.ival = r1->instr->instr->u.ldc.value.u.ival;
                            } 
                            else if(temp->value.format == IMMED_FLOAT)
                            {
                                temp->value.u.fval = r1->instr->instr->u.ldc.value.u.fval;
                            }                            
                            
                            add_constant(&constants, temp);
                        }
                    }                    
                    
                    break;
                }
                case BJ_FORM: {
                    switch(instr->opcode) {
                        case BFALSE_OP: {
                            constant_reg * r1 = isConstant(instr->u.bj.src, constants);
                            if(r1) {
                                rerun = 1;
                                if(r1->value.format == IMMED_INT) {
                                    if(r1->value.u.ival) {
                                        //printf("need to remove %s\n", instr->u.bj.target->name);
                                        add_label_node(&cleanuplist, instr->u.bj.target);
                                        remove_simple_instr(instr);
                                        switch_instr_node_to_nop(current);
                                        if(r1->instr->instr->opcode == LDC_OP) {
                                            //remove_simple_instr(r1->instr->instr);
                                            //switch_instr_node_to_nop(r1->instr);
                                        }
                                    } else {
                                        // jmp

                                    }
                                } else {
                                    if(r1->value.u.fval) {
                                        add_label_node(&cleanuplist, instr->u.bj.target);
                                        remove_simple_instr(instr);
                                        switch_instr_node_to_nop(current);                                     
                                    }
                                }
                            }
                            break;
                        }
                    }
                }
                case LABEL_FORM: {
                    label_node * current_label = cleanuplist;
                    while(current_label) {
                        if(instr->u.label.lab == current_label->l) {
                            //printf("removing label \"%s\"\n", current_label->l->name);
                            remove_simple_instr(instr);
                            switch_instr_node_to_nop(current);
                            rerun = 1;
                            break;
                        }
                        current_label = current_label->next;
                    }
                    break;
                }
                case LDC_FORM: {                
                    constant_reg * temp = (constant_reg *) malloc(sizeof(constant_reg));
                    temp->next = NULL;
                    temp->instr = current;
                    temp->value.format = instr->u.ldc.value.format;
                    if(temp->value.format == IMMED_INT) {
                        temp->value.u.ival = instr->u.ldc.value.u.ival;
                    } 
                    else if(temp->value.format == IMMED_FLOAT)
                    {
                        temp->value.u.fval = instr->u.ldc.value.u.fval;
                    }
                    else { 
                        free(temp);
                        current = current->next;
                        continue;
                    }
                    temp->r = instr->u.ldc.dst;
                    //temp->prev = lastConstant;
                    
                    add_constant(&constants, temp);
                    break;
                }
            }
            current = current->next;
         }
         current_block = current_block->next;
    }

    //printf("\n\nsimple instr\n\n");
   // print_sinstrs(block_head->next->start->instr);
    return rerun;
}

// end of constant folding


void do_reaching_def(basic_block_node * block_head, instr_node * instr_head) {
    block_ptr * stack = NULL;
    instr_ptr * def_instrs = NULL;
    int totalrdefs = find_definitions(instr_head, &def_instrs);
    init_rd_gen_and_kill_sets(block_head, def_instrs, totalrdefs);
    find_predecessors(block_head);
    while(dfa_start(block_head, rd_meetop, rd_transferfunc, &stack, 0)) {
        free_block_ptr(stack);
		stack = NULL;
    }

    free_instr_ptr(def_instrs);
}

int do_loop_invariant_code_motion(loop_block * loops, basic_block_node ** block_head, instr_node ** instr_head) {
	loop_block * current_loop = loops;
	simple_instr * inlist = (*instr_head)->instr;
	int i = 0;
	while(current_loop) {  
        //do_reaching_def(*block_head, *instr_head);
        //printf("loop start %d end %d\n", current_loop->head->block->number, current_loop->tail->block->number);
        //current_loop->preheader = current_loop->head->block->previous->start;
        //optimize_a_loop(current_loop, *block_head, *instr_head);
		if(optimize_a_loop(current_loop, *block_head, *instr_head))           
			break;//return 1;        
		current_loop = current_loop->next;
	}

    return 0;
}



void print_reg(simple_reg * r) {
    if(r->kind == PSEUDO_REG)
        printf("r%d", r->num);
    else
        printf("t%d", r->num);
}

void add_outside_operand(constant_reg ** head, simple_reg * r, constant_reg * inside) {
    constant_reg * tmp;

    constant_reg * c_inside = inside;

    while(c_inside) {
        //print_reg(c_inside->r); printf("\t"); print_reg(r); printf("\n"); 
        if(c_inside->r == r) // its defined inside
            return;
        c_inside = c_inside->next;
    }
    //printf("\n\n");

    tmp = *head;

    while(tmp) {
        if(tmp->r == r)
            return; // already in the list
        tmp = tmp->next;
    }
    
    tmp = (constant_reg *)malloc(sizeof(constant_reg));
    tmp->r = r;
    add_constant(head, tmp);
}

void add_inside_operand(constant_reg ** head, simple_reg * r, constant_reg ** outside) {
    constant_reg * tmp = *outside;
    
    if(*outside && (*outside)->r == r) {
        *outside = (*outside)->next;
        free(tmp);
    } else {     
        constant_reg * prev;
        tmp = *outside;
        while(tmp) {
            if(tmp->r == r)
            {
                prev->next = tmp->next;
                free(tmp);
                break;
            }
            prev = tmp;
            tmp = tmp->next;
        }
    }

    tmp = (constant_reg *)malloc(sizeof(constant_reg));
    tmp->r = r;
    add_constant(head, tmp);
}

basic_block_node * get_ith_block(basic_block_node * block_head, int i) {
    basic_block_node * current_block = block_head;

    while(current_block) {
        if(current_block->number == i)
            return current_block;

        current_block = current_block->next;
    }
}

int count_instr_in_loop(loop_block * loop, basic_block_node * block_head, constant_reg ** definedOutside, constant_reg ** constants) {
    basic_block_node * current_block;
    int i=0, count = 0, j=0;
    constant_reg * definedInside = NULL;

    //for(i=0 ; i < loop->nodes->num_bits; i++) {
        //if(get_bit(loop->nodes, i)) {
    //while(current_block && current_block!=loop->tail->block->next) {
	    for(j=0; j < loop->nodes->num_bits; j++) {
		    if(get_bit(loop->nodes, j)) {			    
			    instr_node * current_instr;
			    current_block = get_ith_block(block_head, j);
			    current_instr = current_block->start;
			    while(current_instr && current_block->end && current_instr != current_block->end->next) {
				simple_instr * instr  = current_instr->instr;
				i++;
				
				switch(simple_op_format(instr->opcode)) {
				    case BASE_FORM:
					if(instr->u.base.src1 && instr->u.base.src1->kind == PSEUDO_REG) {
					   add_outside_operand(definedOutside, instr->u.base.src1, definedInside);
					}
					if(instr->u.base.src2 && instr->u.base.src2->kind == PSEUDO_REG) {
					   add_outside_operand(definedOutside, instr->u.base.src2, definedInside);
					}
					if(instr->u.base.dst && instr->u.base.dst->kind == PSEUDO_REG) {
					   add_inside_operand(&definedInside, instr->u.base.dst, definedOutside);
					}
					break;
				    case LDC_FORM: {
					constant_reg * temp = (constant_reg *) malloc(sizeof(constant_reg));                       
					temp->r = instr->u.ldc.dst;  
					temp->instr = current_instr;
					add_constant(constants, temp);
					//print_reg(temp->r); printf("\n");
		
					if(instr->u.base.dst) { 
					   add_inside_operand(&definedInside, instr->u.ldc.dst, definedOutside);
					}
		
					break;
				    }
				    case CALL_FORM:
				    case BJ_FORM:
				    case MBR_FORM:
				    case LABEL_FORM:
				}
				current_instr = current_instr->next;
			    }
		    }
	    }

    return i;
}


void move_instr(simple_instr * target, simple_instr * after) {
    simple_instr * after_next = after->next;
    simple_instr * target_prev = target->prev;
    simple_instr * target_next = target->next;

    if(target_prev)
        target_prev->next = target_next;
    if(target_next)
        target_next->prev = target_prev;

    after->next = target;
    target->prev = after;
    target->next = after_next;
    if(after_next)
        after_next->prev = target;
}

int move_instrs(loop_block * loop, instr_node * instr_head, int instr_offset) {
    int i;
    int isChanged = 0;
    simple_instr * insertAfter;
    
    if(loop->preheader == NULL)
        return 0;
    insertAfter = loop->preheader->instr;

    for(i= 0; i < loop->invariant_instrs->num_bits; i++) {
        if(get_bit(loop->invariant_instrs, i)) {
            instr_node * target_instr = get_ith_instr(instr_head, i + instr_offset);
            isChanged = 1;
            if(target_instr->instr->opcode == LDC_OP) {
                move_instr(target_instr->instr, insertAfter);
                //printf("iA = %p new = %p\n", insertAfter, target_instr->instr);
                fprint_instr(stdout, insertAfter);
                fprint_instr(stdout, target_instr->instr);
                insertAfter = target_instr->instr;
                switch_instr_node_to_nop(target_instr);                
            } else if(simple_op_format(target_instr->instr->opcode) == BASE_FORM) {
                simple_instr * cpy1 = new_instr(CPY_OP, target_instr->instr->type);                
                simple_reg * r = new_register(target_instr->instr->type, PSEUDO_REG);
                simple_instr * cinstr;
                int found = 0;
                fprint_instr(stdout, target_instr->instr);
                cpy1->u.base.dst = r;
                cpy1->u.base.src1 = target_instr->instr->u.base.dst;
                fprint_instr(stdout, cpy1);
                move_instr(target_instr->instr, insertAfter);
                move_instr(cpy1, target_instr->instr);
                insertAfter = cpy1;

                cinstr = target_instr->next->instr;
                while(cinstr && !found) {
                    switch(simple_op_format(cinstr->opcode)) {
                        case BASE_FORM:
                            if(cinstr->u.base.src1 && cinstr->u.base.src1 == target_instr->instr->u.base.dst)
                            {
                                printf("bfix: "); fprint_instr(stdout, cinstr);
                                cinstr->u.base.src1 = r;
                                found = 1;                                
                                printf("fix: "); fprint_instr(stdout, cinstr);
                            }
                            if(cinstr->u.base.src2 && cinstr->u.base.src2 == target_instr->instr->u.base.dst)
                            {
                                printf("bfix: "); fprint_instr(stdout, cinstr);
                                cinstr->u.base.src2 = r;
                                found = 1;                   
                                printf("fix: ");fprint_instr(stdout, cinstr);
                            }
                            break;
                        case BJ_FORM:
                            if(cinstr->u.bj.src && cinstr->u.bj.src == target_instr->instr->u.base.dst)
                            {
                                printf("bfix: "); fprint_instr(stdout, cinstr);
                                cinstr->u.bj.src = r;
                                found = 1;                   
                                printf("fix: ");fprint_instr(stdout, cinstr);
                            }
                            break;
                    }
                    cinstr = cinstr->next;
                }
            }            
        }
    }
    return isChanged;
}


int optimize_a_loop(loop_block * loop, basic_block_node * block_head, instr_node * instr_head) {    
    int i;
    constant_reg * constants = NULL;
    basic_block_node * current_block = NULL;
    instr_node * current_instr = NULL;
    constant_reg * definedOutside = NULL;
    int totalloopinstrs = count_instr_in_loop(loop, block_head, &definedOutside, &constants);
    int instr_offset = 0;
    constant_reg * tmp ;
    
    printf("number of instrs: %d\n", totalloopinstrs);
    
    tmp = definedOutside;
    printf("\ndefined\n");
    while(tmp) {
        constant_reg * temp = (constant_reg *) malloc(sizeof(constant_reg));
        
        if(tmp->r->kind == PSEUDO_REG) 
            printf("r%d\n", tmp->r->num);
        else
            printf("t%d\n", tmp->r->num);

        temp->r = tmp->r;
        add_constant(&constants, temp);
        tmp = tmp->next;
    }
    
    /*
    printf("\nconstants:\n");
    tmp = constants;
    while(tmp) {
    //    constant_reg * temp = (constant_reg *) malloc(sizeof(constant_reg));
    
        if(tmp->r->kind == PSEUDO_REG) 
            printf("r%d\n", tmp->r->num);
        else
            printf("t%d\n", tmp->r->num);

  //      temp->r = tmp->r;
//        add_constant(&constants, temp);
        tmp = tmp->next;
    }
    */

    loop->invariant_instrs = new_bit_vector(totalloopinstrs);
    
    
    printf("\nloop nodes: ");
    for(i = 0; i < loop->nodes->num_bits; i++)
    	if(get_bit(loop->nodes, i)) {
		if(!instr_offset) {
			current_block = get_ith_block(block_head, i);
			instr_offset = current_block->start->number;
			loop->preheader = current_block->previous->start;
		}
	    printf("%d ", i);
	}
    printf("\n\n");
		    
    printf("instr_offset %d\n", instr_offset);

    //while(current_block && current_block != loop->tail->block->next) {
	for(i = 0; i < loop->nodes->num_bits; i++) {
		if(get_bit(loop->nodes, i)) {
			instr_node * current_instr;
			
			current_block = get_ith_block(block_head, i);
			current_instr  = current_block->start;
			while(current_instr && current_instr != current_block->end->next) {
			    simple_instr * instr = current_instr->instr;
			    switch(simple_op_format(instr->opcode)) {
				case BASE_FORM: 
				{
				    constant_reg * r1 = isConstant(instr->u.base.src1, constants);
				    constant_reg * r2 = isConstant(instr->u.base.src2, constants);
				    //if(r1 && !(instr->u.base.src2)) {
				    //    set_bit(loop->invariant_instrs, current_instr->number - instr_offset, TRUE);
				    //} else 
				    if (r1 && r2) {
					set_bit(loop->invariant_instrs, current_instr->number - instr_offset, TRUE);
					
					if(r2->r->kind == TEMP_REG) {
					    set_bit(loop->invariant_instrs, r2->instr->number - instr_offset, TRUE);
					}
					if(r1->r->kind == TEMP_REG) {
					    set_bit(loop->invariant_instrs, r1->instr->number - instr_offset, TRUE);
					}
				    }
				    break;
				}
			    }
			    current_instr = current_instr->next;
			}
		}
	}

    printf("loop invariant instrs\n");
    for(i=0; i < loop->invariant_instrs->num_bits; i++)
        if(get_bit(loop->invariant_instrs, i))
        {
            instr_node * current_invaritant = get_ith_instr(instr_head, i);
            printf("%d ", i + instr_offset);
            //resolv_dependence(current_invariant, loop->invariant_instrs, instr_offset);
        }
         
    printf("\n\n");
    return move_instrs(loop, instr_head, instr_offset);
}


void look_for_biv_pattern(simple_instr * instr) {
    simple_instr * cinstr = instr;

    while(cinstr) {

        cinstr = cinstr->prev;
    }
}

void find_biv(loop_block * current_loop) {
    basic_block_node * current_block = current_loop->head->block;
    instr_node * current_instr = NULL;
    while(current_block && current_block != current_loop->tail->block->next) {
        current_instr = current_block->start;
        while(current_instr && current_instr != current_block->end->next) {
            simple_instr * instr = current_instr->instr;
            if(instr->opcode == CPY_OP && instr->u.base.dst && instr->u.base.dst->kind == PSEUDO_REG) {
                simple_instr * op = instr->prev;
                if((op->opcode == ADD_OP || op->opcode == SUB_OP)
                    && op->u.base.dst == instr->u.base.src1 && op->u.base.src1 == instr->u.base.dst) {
                    simple_instr * c = op->prev;
                    printf("found cpy at %d and add/sub at %d\n\n", current_instr->number, current_instr->previous->number);
                    if(c->opcode == LDC_OP && c->u.ldc.dst == op->u.base.src2) {
                        if(c->u.ldc.value.format == IMMED_INT)
                            printf("BIV(r%d, 1, %d)\n\n", instr->u.base.dst->num, c->u.ldc.value.u.ival);
                        else
                            printf("BIV(r%d, 1, %f)\n\n", instr->u.base.dst->num, c->u.ldc.value.u.fval);
                    }
                }
            }
            current_instr = current_instr->next;
        }
        current_block = current_block->next;
    }
}

// BIV & DIV to do strength reduction
void do_other_loop_optimizations(loop_block * loop_head) {
    loop_block * current_loop = loop_head;

    while(current_loop) {
        printf("\n\nhead block # %d \ntail block # %d\n", current_loop->head->block->number, current_loop->tail->block->number);
        find_biv(current_loop);
        current_loop = current_loop->next;
    }
}
